#include <bits/stdc++.h>
using namespace std;

/*
1912. 设计电影租借系统
已解答
困难
相关标签
premium lock icon
相关企业
提示
你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。

所有电影用二维整数数组 entries 表示，其中 entries[i] = [shopi, moviei, pricei] 表示商店 shopi 有一份电影 moviei 的拷贝，租借价格为 pricei 。每个商店有 至多一份 编号为 moviei 的电影拷贝。

系统需要支持以下操作：

Search：找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。商店需要按照 价格 升序排序，如果价格相同，则 shopi 较小 的商店排在前面。如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。
Rent：从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。
Drop：在指定商店返还 之前已借出 的指定电影。
Report：返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表 res 返回，其中 res[j] = [shopj, moviej] 表示第 j 便宜的已借出电影是从商店 shopj 借出的电影 moviej 。res 中的电影需要按 价格 升序排序；如果价格相同，则 shopj 较小 的排在前面；如果仍然相同，则 moviej 较小 的排在前面。如果当前借出的电影小于 5 部，则将它们全部返回。如果当前没有借出电影，则返回一个空的列表。
请你实现 MovieRentingSystem 类：

MovieRentingSystem(int n, int[][] entries) 将 MovieRentingSystem 对象用 n 个商店和 entries 表示的电影列表初始化。
List<Integer> search(int movie) 如上所述，返回 未借出 指定 movie 的商店列表。
void rent(int shop, int movie) 从指定商店 shop 借出指定电影 movie 。
void drop(int shop, int movie) 在指定商店 shop 返还之前借出的电影 movie 。
List<List<Integer>> report() 如上所述，返回最便宜的 已借出 电影列表。
注意：测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。

 

示例 1：

输入：
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
输出：
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

解释：
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1);  // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。
movieRentingSystem.rent(0, 1); // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。
movieRentingSystem.rent(1, 2); // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。
movieRentingSystem.report();   // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。
movieRentingSystem.drop(1, 2); // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。
movieRentingSystem.search(2);  // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。
 

提示：

1 <= n <= 3 * 105
1 <= entries.length <= 105
0 <= shopi < n
1 <= moviei, pricei <= 104
每个商店 至多 有一份电影 moviei 的拷贝。
search，rent，drop 和 report 的调用 总共 不超过 105 次。
*/

// 法一
class MovieRentingSystem {
public:
    // init 加载所有商店的电影信息，构建基础映射和可用电影集合
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (auto& entry : entries) {
            int shop = entry[0], movie = entry[1], price = entry[2];
            // 键值对的构建
            uint64_t key = (uint64_t)shop << 32 | movie;
            shop_movie_to_price[key] = price;

            // enter 集合
            available_movies[movie].insert({price, shop});
        }
    }
    
    // 价格→商店号排序
    vector<int> search(int movie) {
        vector<int> ans;

        auto avali_it = available_movies.find(movie);
        if (avali_it == available_movies.end())     return ans;

        // foreach  前五个
        auto& shop_set = avali_it->second;
        for (auto& [price, shop] : shop_set) {
            ans.push_back(shop);
            if (ans.size() == 5)    break;
        }
        return ans;
    }
    
    // 可用集合移到已借出集合
    void rent(int shop, int movie) {
        uint64_t key = (uint64_t)shop << 32 | movie;
        int price = shop_movie_to_price[key];

        // erase 可用集合
        available_movies[movie].erase({price, shop});
        // inser 已借出集合
        rented_movies.insert({price, shop, movie});
    }
    
    // 已借出集合移回可用集合
    void drop(int shop, int movie) {
        // 相反的rent
        uint64_t key = (uint64_t)shop << 32 | movie;
        int price = shop_movie_to_price[key];

        rented_movies.erase({price, shop, movie});
        available_movies[movie].insert({price, shop});
    }
    
    // 生成已借出电影报告：返回最便宜的5部（按价格→商店号→电影号排序）
    vector<vector<int>> report() {
        vector<vector<int>> ans;
        for (auto& [price, shop, movie] : rented_movies) {
            ans.push_back({shop, movie});
            if (ans.size() == 5)    break;
        }
        return ans;
    }

private:
    // （商店，电影）→ 价格的映射，快速获取固定价格（O(1)）
    // 键：(shop << 32) | movie（用uint64_t避免哈希冲突，无需自定义哈希）
    unordered_map<uint64_t, int> shop_movie_to_price;
    // 未借出的电影：电影ID → 有序集合（价格升序，价格相同则商店号升序）
    // 集合元素：(price, shop)，满足search的排序需求（set自动维护有序）
    unordered_map<int, set<pair<int, int>>> available_movies;
    // 已借出的电影：有序集合（价格升序 → 商店号升序 → 电影号升序）
    // 集合元素：(price, shop, movie)，满足report的排序需求（tuple默认按元素顺序排序）
    set<tuple<int, int, int>> rented_movies;

};

/**
 * Your MovieRentingSystem object will be instantiated and called as such:
 * MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
 * vector<int> param_1 = obj->search(movie);
 * obj->rent(shop,movie);
 * obj->drop(shop,movie);
 * vector<vector<int>> param_4 = obj->report();
 */

// 法二
class MovieRentingSystem {
private:
    // 自定义哈希函数：为(shop, movie)对生成哈希值，优化unordered_map查找效率
    static constexpr auto pairHash = [fn = hash<int>()](const pair<int, int>& o) {
        return (fn(o.first) << 16) ^ fn(o.second); // 组合shop和movie的哈希值，减少碰撞
    };
    // 存储(shop, movie)→price的映射：O(1)获取固定价格，支撑rent/drop操作
    unordered_map<pair<int, int>, int, decltype(pairHash)> t_price{0, pairHash};

    // 存储未借出电影：movie→set{(price, shop)}，set自动按"价格升序→shop升序"排序
    // 直接满足search操作的排序需求，避免额外排序开销
    unordered_map<int, set<pair<int, int>>> t_valid;

    // 存储已借出电影：set{(price, shop, movie)}，tuple自动按"价格→shop→movie"升序排序
    // 直接满足report操作的排序需求，天然维护有序性
    set<tuple<int, int, int>> t_rent;

public:
    // 初始化：加载所有电影信息，构建价格映射和初始可用集合
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (const auto& entry: entries) {
            int shop = entry[0], movie = entry[1], price = entry[2];
            t_price[{shop, movie}] = price;          // 记录固定价格
            t_valid[movie].emplace(price, shop);     // 初始状态均为未借出，加入可用集合
        }
    }
    
    // 查找未借出的指定电影：返回最便宜的5个商店（按价格→shop排序）
    vector<int> search(int movie) {
        if (!t_valid.count(movie)) return {}; // 该电影无可用商店
        
        vector<int> ret;
        auto& shopSet = t_valid[movie];
        // 遍历有序集合，取前5个商店（已按规则排序）
        for (auto it = shopSet.begin(); it != shopSet.end() && ret.size() < 5; ++it) {
            ret.push_back(it->second); // 取商店号
        }
        return ret;
    }
    
    // 租借操作：从可用集合移至已借出集合
    void rent(int shop, int movie) {
        int price = t_price[{shop, movie}];       // 获取固定价格
        t_valid[movie].erase({price, shop});      // 从可用集合移除
        t_rent.emplace(price, shop, movie);       // 加入已借出集合
    }
    
    // 返还操作：从已借出集合移回可用集合
    void drop(int shop, int movie) {
        int price = t_price[{shop, movie}];       // 获取固定价格
        t_valid[movie].emplace(price, shop);      // 加回可用集合
        t_rent.erase({price, shop, movie});       // 从已借出集合移除
    }
    
    // 生成已借出电影报告：返回最便宜的5部（按价格→shop→movie排序）
    vector<vector<int>> report() {
        vector<vector<int>> ret;
        // 遍历有序集合，取前5部电影（已按规则排序）
        for (auto it = t_rent.begin(); it != t_rent.end() && ret.size() < 5; ++it) {
            ret.push_back({get<1>(*it), get<2>(*it)}); // 取(shop, movie)
        }
        return ret;
    }
};

// 法三 
class MovieRentingSystem {
    // 存储(shop, movie)→price的映射：用1LL*shop<<32|movie将两者合并为64位键，避免自定义哈希，提升查找效率
    unordered_map<long long, int> sm2p;
    // 存储未借出电影：key=movie，value=set{(price, shop)}，set自动按"价格升序→shop升序"排序，直接满足search需求
    unordered_map<int, set<pair<int, int>>> unrent2ps;
    // 存储已借出电影：set{(price, shop, movie)}，tuple自动按"价格→shop→movie"升序排序，直接满足report需求
    set<tuple<int, int, int>> rentm;

public:
    // 初始化：加载电影信息，构建价格映射和初始未借出集合
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (auto& e : entries) {
            int shop = e[0], movie = e[1], price = e[2];
            sm2p[1LL * shop << 32 | movie] = price;  // 合并shop和movie为64位键
            unrent2ps[movie].emplace(price, shop);    // 初始状态为未借出，加入对应集合
        }
    }
    
    // 查找未借出的指定电影：返回价格最低的前5个商店（依赖set的自然排序）
    vector<int> search(int movie) {
        auto it = unrent2ps.find(movie);
        if (it == unrent2ps.end()) return {};  // 无可用商店
        
        vector<int> ans;
        // 遍历有序集合，取前5个商店（已按价格→shop排序）
        for (auto [_, shop] : it->second) {
            ans.push_back(shop);
            if (ans.size() == 5) break;
        }
        return ans;
    }
    
    // 租借操作：从"未借出"移至"已借出"集合
    void rent(int shop, int movie) {
        int price = sm2p[1LL * shop << 32 | movie];  // 获取固定价格
        unrent2ps[movie].erase({price, shop});       // 从可用集合移除
        rentm.emplace(price, shop, movie);           // 加入已借出集合
    }
    
    // 返还操作：从"已借出"移回"未借出"集合
    void drop(int shop, int movie) {
        int price = sm2p[1LL * shop << 32 | movie];  // 获取固定价格
        rentm.erase({price, shop, movie});           // 从已借出集合移除
        unrent2ps[movie].emplace(price, shop);       // 加回可用集合
    }
    
    // 生成已借出电影报告：返回价格最低的前5部（依赖set的自然排序）
    vector<vector<int>> report() {
        vector<vector<int>> ans;
        // 遍历有序集合，取前5部电影的(shop, movie)（已按价格→shop→movie排序）
        for (auto [_, shop, movie] : rentm) {
            ans.push_back({shop, movie});
            if (ans.size() == 5) break;
        }
        return ans;
    }
};

/**
 * Your MovieRentingSystem object will be instantiated and called as such:
 * MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
 * vector<int> param_1 = obj->search(movie);
 * obj->rent(shop,movie);
 * obj->drop(shop,movie);
 * vector<vector<int>> param_4 = obj->report();
 */


//////////////////////////////////////////////
// 合并键值有太多种了 只是为了避免hash冲突
//////////////////////////////////////////////